package com.liyghting.datastructurealgorithm.sort;

/**
 * 分治和分区思想
 * 找到分区点，把数组分为小于分区点数组，分区点，大于分区点数组
 * 直到区间距离为1为止
 * 递归处理
 * 快排是不稳定原地排序算法，适合大数据集排序
 * 平均时间复杂度O(nlogn),极端情况会退化为O(n^2)
 * 空间复杂度O(1)
 * @author LiYiGuang
 * @date 2018/11/30 14:18
 */
public class QuickSort {

	public static void quickSort(int[] arr, int n) {
		quickSortC(arr, 0, n - 1);
	}

	/**
	 * 快排递归
	 * 
	 * @param arr
	 * @param p
	 *            下标
	 * @param r
	 */
	private static void quickSortC(int[] arr, int p, int r) {
		if (p >= r) return;
		int q = partition(arr, p, r);
		quickSortC(arr, p, q - 1);
		quickSortC(arr, q + 1, r);
	}

	/**
	 * 获取分区点
	 * 
	 * @param arr
	 * @param p
	 * @param r
	 * @return
	 */
	private static int partition(int[] arr, int p, int r) {
		int pivot = arr[r];
		int i = p;
		for (int j = p; j < r; j++) {
			if (arr[j] < pivot) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				i++;
			}
		}
		arr[r] = arr[i];
		arr[i] = pivot;
		return i;
	}

	private static void printAll(int[] arr, int n) {
		for (int i = 0; i < n; i++) {
			System.out.print(arr[i] + ",");
		}
		System.out.println();
	}

	public static void main(String[] args) {

		int[] arr = new int[] { 11, 8, 3, 9, 7, 1, 2, 5 };
		quickSort(arr, 8);
		printAll(arr, 8);
	}

}